1385F - Removing Leaves - CodeForces Solution

// Hydro submission #64df1d3896648c256e881d4d@1692345553318
#include<bits/stdc++.h>
using namespace std;

int n,k;
set<int> to[200001],leaf[200001];
priority_queue<pair<int,int> > Q;

void init(int id,int father){
    for(int v :to[id])
        if(v!=father){
            init(v,id);
            if(to[v].size()==1)
                leaf[id].insert(v);
        }
    if(to[id].size()==1)
        for(int v :to[id])
            if(v!=father){
                init(v,id);
                leaf[v].insert(id);
            }
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        while(!Q.empty())Q.pop();
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            to[i].clear(),leaf[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            to[u].insert(v);
            to[v].insert(u);
        }
        if(k==1){
            printf("%d\n",n-1);
            continue;
        }
        init(1,0);
        for(int i=1;i<=n;i++)
            if(leaf[i].size()>=k)
                Q.push({leaf[i].size(),i});
        int total=0;
        while(!Q.empty()){
            int u=Q.top().second; Q.pop();
            while(leaf[u].size()>=k){
                for(int i=1;i<=k;i++)
                    to[u].erase(*(leaf[u].begin())),
                    leaf[u].erase(leaf[u].begin());
                total++;
            }
            if(to[u].size()==1){
                int fa=*(to[u].begin());
                leaf[fa].insert(u);
                if(leaf[fa].size()>=k)
                    Q.push({leaf[fa].size(),fa});
            }
        }
        printf("%d\n",total);
    }
    return 0;
}